home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2000 / MacHack 2000.toast / pc / The Hacks / Genie / Projects / Anagaal / Source / Includes / NGLList.hh < prev   
Encoding:
Text File  |  2000-06-24  |  6.5 KB  |  338 lines
  1. /*    ==========
  2.  *    NGLList.hh
  3.  *    ==========
  4.  *    
  5.  *    Copyright 1996-2000 Joshua Juran
  6.  */
  7.  
  8. /*
  9.     This program is free software; you can redistribute it and/or modify
  10.     it under the terms of the GNU General Public License as published by
  11.     the Free Software Foundation; either version 2 of the License, or
  12.     (at your option) any later version.
  13.  
  14.     This program is distributed in the hope that it will be useful,
  15.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.     GNU General Public License for more details.
  18.  
  19.     You should have received a copy of the GNU General Public License
  20.     along with this program; if not, write to the Free Software
  21.     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22. */
  23.  
  24. #pragma once
  25.  
  26. #include <stddef.h>
  27.  
  28.  
  29. //    NGLListNode
  30. //    -----------
  31.  
  32. template <class Type>
  33. class NGLListNode {
  34.     friend class NGLList;
  35. public:
  36.     NGLListNode(Type inNewDatum)
  37.         : mNext(NULL), mDatum(inNewDatum), mWasDeleted(false) {}
  38.     ~NGLListNode() {}
  39.     void AddNext(Type inNewDatum);
  40.     NGLListNode<Type> *RemoveNext();
  41.     NGLListNode<Type> *Next() const {return mNext;}
  42.     Type Datum() const {return mDatum;}
  43.     bool WasDeleted() const {return mWasDeleted;}
  44.     void MarkDeleted() {mWasDeleted = true;}
  45. public:  // Changed to public because SCpp doesn't know what 'friend' means
  46.     NGLListNode<Type> *mNext;
  47.     Type mDatum;
  48.     bool mWasDeleted;
  49. };
  50.  
  51. template <class Type>
  52. void
  53. NGLListNode<Type>::AddNext(Type inNewDatum)
  54. {
  55.     NGLListNode<Type> *node(inNewDatum);
  56.     node->mNext = mNext;
  57.     mNext = node;
  58. }
  59.  
  60. template <class Type>
  61. NGLListNode<Type> *
  62. NGLListNode<Type>::RemoveNext()
  63. {
  64.     NGLListNode<Type> *node = mNext;
  65.     mNext = mNext->mNext;
  66.     return node;
  67. }
  68.  
  69.  
  70. //    NGLList
  71. //    -------
  72.  
  73. template <class Type>
  74. class NGLList {
  75. // For debugging
  76. private:
  77.     unsigned long mNote;
  78. public:
  79.     NGLList() : mNote('list'), mHead(NULL), mRefCount(0) {}
  80.     ~NGLList();
  81.  
  82. protected:
  83.     NGLListNode<Type> *HeadNode() const {return mHead;}
  84.     // No, that's not a typo. No need to zero both of them.
  85.     NGLListNode<Type> *TailNode() const {return mHead ? mTail : NULL;}
  86.     NGLListNode<Type> *FindNode(Type inDatum) const;
  87.  
  88. public:
  89.     typedef void (*NGLUserFunc)(Type inDatum, void *inUserCon);
  90.     
  91. public:
  92.     Type FirstDatum() const {return HeadNode() ? HeadNode()->Datum() : NULL;}
  93.     Type LastDatum() const {return TailNode() ? TailNode()->Datum() : NULL;}
  94.     Type Successor(Type inDatum) const {
  95.         return (FindNode(inDatum) && FindNode(inDatum)->Next())
  96.             ? FindNode(inDatum)->Next()->Datum()
  97.             : (Type)NULL;
  98.     }
  99.     
  100.     long Count() const;
  101.     Type GetIndDatum(long inIndex) const;
  102.     void Prepend(Type inNewDatum);
  103.     void Append(Type inNewDatum);
  104.     Type Behead();
  105.     void Remove(Type inVictim);
  106.     void RemoveAll();
  107.     void ForEach(NGLUserFunc inFunc, void *inUserCon);
  108.     NGLListNode<Type> *BeginIteration();
  109.     void EndIteration();
  110.     
  111. protected:
  112.     NGLListNode<Type> *mHead;
  113.     NGLListNode<Type> *mTail;
  114.     long mRefCount;
  115. };
  116.  
  117. // Template class member function definitions
  118.  
  119. template <class Type>
  120. NGLList<Type>::~NGLList()
  121. {
  122.     NGLListNode<Type> *node = mHead;
  123.     
  124.     while (node) {
  125.         NGLListNode<Type> *ondeck = node->Next();
  126.         //Type victim = node->Datum();
  127.         delete node;
  128.         //delete victim;
  129.         node = ondeck;
  130.     }
  131. }
  132.  
  133.  
  134. template <class Type>
  135. NGLListNode<Type> *
  136. NGLList<Type>::FindNode(Type inDatum) const
  137. {
  138.     NGLListNode<Type> *node = mHead;
  139.     
  140.     for (node = mHead; node; node = node->Next())
  141.         if (node->Datum() == inDatum)
  142.             return node;
  143.     
  144.     return NULL;
  145. }
  146.  
  147.  
  148. template <class Type>
  149. long
  150. NGLList<Type>::Count() const
  151. {
  152.     long count = 0;
  153.     NGLListNode<Type> *node = mHead;
  154.     while (node) {
  155.         count++;
  156.         node = node->Next();
  157.     }
  158.     return count;
  159. }
  160.  
  161. template <class Type>
  162. Type
  163. NGLList<Type>::GetIndDatum(long inIndex) const
  164. {
  165.     long count = 0;
  166.     NGLListNode<Type> *node = mHead;
  167.     while (node) {
  168.         if (inIndex-- == 0) {
  169.             return node->Datum();
  170.         }
  171.         node = node->Next();
  172.     }
  173.     return (Type)NULL;
  174. }
  175.  
  176. template <class Type>
  177. void
  178. NGLList<Type>::Prepend(Type inNewDatum)
  179. {
  180.     if (!mHead) mHead = mTail = new NGLListNode<Type>(inNewDatum);
  181.     else {
  182.         NGLListNode<Type> *head = new NGLListNode<Type>(inNewDatum);
  183.         head->mNext = mHead;
  184.         mHead = head;
  185.     }
  186. }
  187.  
  188.  
  189. template <class Type>
  190. void
  191. NGLList<Type>::Append(Type inNewDatum)
  192. {
  193.     if (!mHead) mHead = mTail = new NGLListNode<Type>(inNewDatum);
  194.     else {
  195. #if 0
  196.         NGLListNode<Type> *last = mHead;
  197.         while (last->Next())
  198.             last = last->Next();
  199.         last = new NGLListNode<Type>(inNewDatum);
  200.         mTail = last;
  201. #endif
  202.         mTail->mNext = new NGLListNode<Type>(inNewDatum);
  203.         mTail = mTail->mNext;
  204.     }
  205. }
  206.  
  207.  
  208. template <class Type>
  209. Type
  210. NGLList<Type>::Behead()
  211. {
  212.     if (!mHead) return NULL;
  213.     Type datum = mHead->mDatum;
  214.     if (mRefCount > 0) {
  215.         mHead->MarkDeleted();
  216.     } else {
  217.         NGLListNode<Type> *head = mHead;
  218.         mHead = mHead->mNext;
  219.         delete head;
  220.     }
  221.     return datum;
  222. }
  223.  
  224.  
  225. template <class Type>
  226. void
  227. NGLList<Type>::Remove(Type inVictim)
  228. {
  229.     // Check for an empty list.
  230.     if (!mHead) return;
  231.     
  232.     NGLListNode<Type> *pred = mHead;
  233.     
  234.     // Check for special case: match on first item.
  235.     if (mHead->Datum() == inVictim) {
  236.         if (mRefCount > 0) {
  237.             pred->MarkDeleted();
  238.         } else {
  239.             mHead = mHead->Next();
  240.             delete pred;
  241.         }
  242.         return;
  243.     }        
  244.     while (pred->Next()) { // List of one item stops here.
  245.         if (pred->Next()->Datum() == inVictim) {
  246.             if (mRefCount > 0) {
  247.                 pred->Next()->MarkDeleted();
  248.             } else {
  249.                 if (pred->Next() == mTail) {
  250.                     mTail = pred;
  251.                 }
  252.                 delete pred->RemoveNext();
  253.             }
  254.             return;
  255.         }
  256.         pred = pred->Next();
  257.     }
  258.     // Couldn't find it.
  259. }
  260.  
  261.  
  262. template <class Type>
  263. void
  264. NGLList<Type>::RemoveAll()
  265. {
  266.     if (mRefCount > 0) {
  267.         NGLListNode<Type> *node = mHead;
  268.         while (node) {
  269.             node->MarkDeleted();
  270.             node = node->Next();
  271.         }
  272.     } else {
  273.         while (mHead) {
  274.             NGLListNode<Type> *node = mHead;
  275.             mHead = node->Next();
  276.             delete node;
  277.         }
  278.     }
  279. }
  280.  
  281.  
  282. template <class Type>
  283. void
  284. NGLList<Type>::ForEach(NGLUserFunc inFunc, void *inUserCon)
  285. {
  286.     NGLListNode<Type> *node = mHead;
  287.     
  288.     while (node) {
  289.         (*inFunc)(node->Datum(), inUserCon);
  290.         node = node->Next();
  291.     }
  292. }
  293.  
  294. template <class Type>
  295. NGLListNode<Type> *
  296. NGLList<Type>::BeginIteration()
  297. {
  298.     mRefCount++;
  299.     
  300.     NGLListNode<Type> *node = mHead;
  301.     
  302.     while (node && node->WasDeleted()) {
  303.         node = node->Next();
  304.     }
  305.     
  306.     return node;
  307. }
  308.  
  309. template <class Type>
  310. void
  311. NGLList<Type>::EndIteration()
  312. {
  313.     mRefCount--;
  314.     
  315.     if (mRefCount == 0) {
  316.         // Purge deleted nodes
  317.         while (mHead && mHead->WasDeleted()) {
  318.             NGLListNode<Type> *node = mHead;
  319.             mHead = mHead->Next();
  320.             delete node;
  321.         }
  322.         if (mHead) {
  323.             NGLListNode<Type> *pred = mHead;
  324.             while (pred->Next()) {
  325.                 if (pred->Next()->WasDeleted()) {
  326.                     if (pred->Next() == mTail) {
  327.                         mTail = pred;
  328.                     }
  329.                     delete pred->RemoveNext();
  330.                 } else {
  331.                     pred = pred->Next();
  332.                 }
  333.             }
  334.         }
  335.     }
  336. }
  337.  
  338.